home *** CD-ROM | disk | FTP | other *** search
/ PC Media 22 / PC MEDIA CD22.iso / share / prog / datalib2 / indclus.cpp < prev    next >
Encoding:
C/C++ Source or Header  |  1995-08-14  |  12.4 KB  |  466 lines
  1. #include "datapriv.hpp"
  2.  
  3. /*
  4.    This file contains the routines concerned with the generation and use
  5.    of indclus structures and indpt structures
  6. */
  7.  
  8. /**********************************************************************************
  9.  
  10. INDPT Routines
  11.  
  12. ***************************************************************************/
  13.  
  14. // Constructor, call with cluster number, parent and index
  15.  
  16. indpt::indpt(long nclus,indpt *iparent,index *oi)
  17. {
  18.  currec=-1;
  19.  parent=iparent;
  20.  indclus *pi=(parent) ? parent->icp : 0;
  21.  
  22.  indclus *ip;
  23.  
  24.  ip=oi->topind;
  25.  while(ip)
  26.  {
  27.   if ((ip->clusn==nclus) && ip->valid) break;
  28.   ip=ip->next;
  29.  }
  30.  
  31.  if (ip)
  32.  {
  33.   icp=ip;                // Set pointer to existing buffer
  34.   if (parent) ip->parent=parent->icp;   // Update parent - may have changed
  35.   else ip->parent=0;
  36.   ip->nuse++;
  37.  }
  38.  else
  39.  {
  40.  
  41.   // Here if we have more clusters in memory than MAXCLUSM, then
  42.   // run thru all clusters, invalid clusters have higher priority
  43.   // for deletion than record clusters, which have higher priority
  44.   // than pointer clusters
  45.  
  46.   if (oi->nclus>MAXCLUSM)    // Look for clusters to delete
  47.   {
  48.    indclus *dip=0;
  49.    int diptype=0;    // 0=all, 1=pointer, 2=record
  50.  
  51.    ip=oi->topind;
  52.    while(ip)
  53.    {
  54.     if (!ip->nuse)
  55.     {
  56.      if (!ip->valid) {dip=ip; break;}
  57.      if (diptype<3 && !ip->clustyp) {dip=ip; diptype=2;}
  58.      if (diptype<2 && ip->clustyp) {dip=ip; diptype=1;}
  59.     }
  60.     ip=ip->next;
  61.    }
  62.    if (dip && (dip!=oi->topind)) delete dip;
  63.   }
  64.   icp=new indclus(nclus,pi,oi);
  65.   icp->nuse++;
  66.  }
  67. }
  68.  
  69. // Construct with pointer to indclus
  70.  
  71. indpt::indpt(indclus *ip)
  72. {
  73.  icp=ip;
  74.  currec=-1;
  75.  parent=0;
  76.  icp->nuse++;
  77. }
  78.  
  79. // Destructor, check if indclus is in use by someone else, otherwise delete
  80.  
  81. indpt::~indpt()
  82. {
  83.  icp->nuse--;
  84.  
  85.  // delete invalid or record clusters now
  86.  
  87.  if (!(icp->nuse) && (icp!=icp->oi->topind) &&
  88.      (!(icp->valid) || !(icp->clustyp))) delete icp;
  89. }
  90.  
  91. /******** Select a record by key value in indpt ***************************/
  92.  
  93. // Call with a top level level indpt, constructs a tree to the nearest
  94. // record, and returns with at pointer to the end of the tree.
  95. // containing the record.
  96. // num is OPINT or OPSTR for string or double result
  97. // ret is 0 if found, or the error code if not
  98. // i is the number of the record
  99.  
  100. indpt *indpt::selkey(char *ivalue,int num,int &ret,int &i)
  101. {
  102.  char value[128],ws[16];
  103.  if (num!=OPINT) {strncpy(value,ivalue,120); value[icp->explen]=0;}
  104.  else *(double *)value=*(double *)ivalue;
  105.  indpt *curind=this;
  106.  int lnum=curind->icp->oi->restype;
  107.  if (lnum==OPDATE) value[8]=0;        // Chop off unwanted bits of date
  108.  
  109.  currec=-1; ret=-1;
  110.  
  111.  if (!icp->nclusrec) {ret=NOKEY; i=0; return this;}   // 0 length index
  112.  
  113.  // Now in each cluster search for the record greater than or equal to value
  114.  do
  115.  {
  116.   double cr;    // compare result
  117.   int re=0;    // Flag reached end of cluster with this record
  118.   int rchk;    // No. of records to check in this cluster
  119.  
  120.   rchk=curind->icp->nclusrec-curind->icp->clustyp;
  121.  
  122.   char *keyp=curind->icp->clusdat+12;
  123.  
  124.   for(i=0; i<rchk; i++)
  125.   {
  126.    if (lnum==OPINT) cr=*(double *)keyp-*(double *)value;
  127.    if (lnum==OPSTR) cr=strcmpdb(keyp,value,curind->icp->explen);
  128.    if (lnum==OPDATE) {strcpy(ws,keyp); ws[8]=0; cr=atol(ws)-atol(value);}
  129.    if (cr>=0) break;
  130.  
  131.    keyp+=icp->reclen;
  132.   }
  133.  
  134.   if (i==curind->icp->nclusrec) {i--; re=1;}    // Reached end, set to last
  135.   curind->currec=i;            // Set next record to be read
  136.  
  137.   if (!curind->icp->clustyp) // Down to the nearest key so quit
  138.   {
  139.    if (!cr) ret=0; else ret=(re) ? NOKEYHIGHER : NOKEY;
  140.   }
  141.   else
  142.   {
  143.    curind=new indpt(*(long *)
  144.                      (curind->icp->clusdat+4+i*curind->icp->reclen),curind,
  145.                        curind->icp->oi);
  146.   }
  147.  }
  148.  while(ret==-1);
  149.  
  150.  return curind;
  151. }
  152.  
  153. /***************************************************************
  154.  
  155. INDCLUS Routines
  156.  
  157. ***************************************************************/
  158.  
  159. // Constructor, call with cluster number, parent and index
  160. // if iclusn the cluster no. is -1 then create a new cluster at
  161. // the end of the file
  162.  
  163. indclus::indclus(long iclusn,indclus *iparent,index *iip)
  164. {
  165.  oi=iip;
  166.  fp=oi->fp;
  167.  parent=iparent;
  168.  clusn=iclusn;
  169.  change=0;
  170.  next=0;
  171.  prev=0;
  172.  nuse=0;
  173.  valid=1;
  174.  oi->nclus++;
  175.  
  176.  if (clusn==-1)        // New cluster
  177.  {
  178.   clusn=oi->lblk++;
  179.   oi->chng=1;
  180.   change=1;
  181.   clustyp=0;
  182.   nclusrec=0;
  183.   memset(clusdat,0,512);
  184.  }
  185.  else            // Read existing cluster
  186.  {
  187.   Fseek(fp,iclusn*512L,SEEK_SET);
  188.   Fread(clusdat,1,512,fp);
  189.   nclusrec=*(int *)(clusdat);
  190.   clustyp=(*(long *)(clusdat+4)>0L) ? 1 : 0;
  191.   if (clustyp) nclusrec++;
  192.  }
  193.  
  194.  if (oi->topind)
  195.  {
  196.   reclen=oi->topind->reclen;
  197.   explen=oi->topind->explen;
  198.   next=oi->topind->next;
  199.   prev=oi->topind;
  200.   oi->topind->next=this;
  201.   if (next) next->prev=this;
  202.  
  203.  }
  204. }
  205.  
  206. // Destructor, clean up pointers, write to disk if changed
  207.  
  208. indclus::~indclus()
  209. {
  210.  if (next) next->prev=prev;
  211.  if (prev) prev->next=next;
  212.  if (oi->topind==this) oi->topind=next;
  213.  if (change && valid)
  214.    { Fseek(fp,clusn*512L,SEEK_SET); Fwrite(clusdat,1,512,fp); }
  215.  oi->nclus--;
  216. }
  217.  
  218. // Subtract record n from a cluster, if the cluster becomes 0 length
  219. // then delete it and move round the file
  220.  
  221. void indclus::subtract(int cr)
  222. {
  223.  if (nclusrec>1)            // Cluster still has records
  224.  {
  225.   int dst=4+cr*reclen;            // Points to key to be removed
  226.   int src=dst+reclen;            // Points past key to be removed
  227.   int nb=512-src;            // No. of bytes to move
  228.   memmove(clusdat+dst,clusdat+src,nb);    // Move the data
  229.   nclusrec--;
  230.   (*((long *)clusdat))--;
  231.   change=1;
  232.  
  233.   // Now we check all parents to see if we need to change the last record
  234.   // key as a result of subtracting this one.
  235.  
  236.   indclus *ci=this;
  237.   cr--;                        // Reduce record number
  238.   while (cr==ci->nclusrec-1 && ci->parent)
  239.   {
  240.    char *ptr=ci->parent->clusdat+4;
  241.    while(*(long *)ptr!=ci->clusn) ptr+=reclen;
  242.    ptr+=8;
  243.    memmove(ptr,ci->clusdat+12+cr*reclen,explen);
  244.    ci->parent->change=1;
  245.    cr=((ptr-ci->parent->clusdat)-12)/reclen;      // record number in parent
  246.    ci=ci->parent;
  247.   }
  248.   return;
  249.  }
  250.  
  251.  // Now there are NO records left in this cluster
  252.  
  253.  if (!parent)    // Very top of tree so don't delete this record !
  254.  {
  255.   memset(clusdat,0,512);
  256.   *(long *)clusdat=0-clustyp;        // Indicate no records at top of tree
  257.   nclusrec=0;
  258.   change=1;
  259.   return;
  260.  }
  261.  
  262.  // Remove this cluster from its parent
  263.  
  264.  indclus *pp=parent;
  265.  int rn=0;            // Find key of this cluster in parent
  266.  
  267.  char *ptr=pp->clusdat+4;
  268.  while(*(long *)ptr!=clusn) {ptr+=reclen; rn++;}
  269.  pp->subtract(rn);
  270.  
  271.  // Maybe we are deleting the last block, if so don't move anything
  272.  
  273.  if (clusn==oi->lblk-1) {oi->lblk--; oi->chng=1; return;}
  274.  
  275.  // Now move the last block into the space occupied by this
  276.  
  277.  indpt bm(oi->lblk-1,0,oi);        // Block to move
  278.  valid=0;                // Discard this block
  279.  
  280.  indpt *pbl=bm.icp->findptr(rn);        // Find pointer to block
  281.  
  282.  if (pbl)
  283.  {
  284.   *(long *)(pbl->icp->clusdat+4+reclen*rn)=clusn;    // Readjust cluster
  285.   pbl->icp->change=1;
  286.  
  287.   indpt *npt;
  288.   while(pbl->parent) {npt=pbl->parent; delete pbl; pbl=npt;} delete pbl;
  289.  }
  290.  else    // Moved block is the top of the tree
  291.  {
  292.   oi->tblk=clusn;
  293.  }
  294.  
  295.  bm.icp->clusn=clusn;
  296.  bm.icp->change=1;        // Flag bm to be written to disk
  297.  oi->lblk--;
  298.  oi->chng=1;
  299. }
  300.  
  301. // Find the cluster which points at the supplied block, and
  302. // construct a tree to it, return the tree, or 0 if the supplied cluster
  303. // is the top block, note the indclus which calls this routine does
  304. // not have to be part of the tree structure
  305. // rn returns the record number in the block
  306.  
  307. indpt *indclus::findptr(int &rn)
  308. {
  309.  if (clusn==oi->tblk) return 0;        // Top block
  310.  
  311.  int dum,dum2;
  312.  indpt *bt=0;                // Bottom of tree after search
  313.  char *pt;                // Pointer to record numbers
  314.  indpt *nt;                // Useful pointer
  315.  
  316.  void *val=clusdat+12;            // First value in block
  317.  indpt *fi=new indpt(oi->topind);    // fi is the top index
  318.  
  319.  bt=fi->selkey((char *)val,oi->indtype,dum,dum2); // Get key matching 1st item
  320.  if (!bt->parent) {delete fi; return 0;}
  321.  
  322.  while(1)
  323.  {
  324.   if (bt->icp->clustyp)        // Ignore a record cluster, go back to parent
  325.   {
  326.    pt=bt->icp->clusdat+4+(bt->currec)*reclen;        // Next rec. no.
  327.    if (*(long *)pt==clusn) break;            // Found It !
  328.   }
  329.   nt=bt->parent; delete bt; bt=nt;    // Get parent record
  330.   if (!bt) {dbfer(NODELKEY); break;}     // At top ? then error
  331.  }
  332.  
  333.  rn=bt->currec;
  334.  return bt;
  335. }
  336.  
  337. // Add a record to the index file
  338. // Call with the right cluster, if we can insert a record do so,
  339. // if not split the current cluster and adjust the parents
  340.  
  341. // newkey is the key to be added
  342. // rn is the record no. associated with the key
  343. // irn is the no. of the next highest record in the cluster, or the
  344. // next lower if rsk is NOKEYHIGHER (ie the key is the last to be added)
  345.  
  346. // Returns index of new cluster if it exists, or 0 if none
  347.  
  348. int indclus::add(char *newkey,long rn,int irn,int rsk)
  349. {
  350.  change=1;        // Well we are going to change this cluster
  351.  
  352.  if (nclusrec<oi->maxclusrec)    // We can fit in an extra record
  353.  {
  354.   int src,dst,nb;    // source, destination & no. of bytes
  355.  
  356.   nclusrec++; (*((long *)clusdat))++;        // New no. of records
  357.  
  358.   if (rsk==NOKEYHIGHER)        // Add to end of this one
  359.   {
  360.    src=(irn+1)*reclen+4;                // Move to end
  361.    *(long *)(clusdat+src+reclen)=0;            // Clear following
  362.    if (parent) parent->newkey(clusn,newkey,clusn);
  363.   }
  364.   else
  365.   {
  366.    src=irn*reclen+4;        // Where to make space
  367.    dst=src+reclen;        // Where to move up
  368.    nb=512-dst;            // No. of bytes
  369.    memmove(clusdat+dst,clusdat+src,nb);    // Move up
  370.   }
  371.   memset(clusdat+src,0,8);            // Clear existing rubbish
  372.   *(long *)(clusdat+src+4*(1-clustyp))=rn;    // Write in record number
  373.   memmove(clusdat+src+8,newkey,explen);        // Copy key
  374.   return 0;
  375.  }
  376.  
  377.  // Now we have to insert a new block
  378.  
  379.  indclus newclus(-1,0,oi);    // Create a new block full of 0's
  380.  newclus.clustyp=clustyp;    // Same cluster type as this
  381.  int nrn=nclusrec/2;        // New no. of records in this cluster
  382.  int nnew=nclusrec-nrn;        // No. of records in the new cluster
  383.  int src=4+nrn*reclen;        // Location to chop cluster in half
  384.  
  385.  memmove(newclus.clusdat+4,clusdat+src,512-src);    // Copy
  386.  memset(clusdat+src,0,8);            // Clear end
  387.  *(long *)(clusdat)=nrn-clustyp; nclusrec=nrn;
  388.  *(long *)(newclus.clusdat)=nnew-clustyp; newclus.nclusrec=nnew;
  389.  char *last=clusdat+src-reclen+8;
  390.  
  391.  // Now find location in parent to insert the new block
  392.  
  393.  char *newlast=newclus.clusdat+(newclus.nclusrec-1)*reclen+12;
  394.  
  395.  if (parent)
  396.  {
  397.   int rv;
  398.   int i=parent->newkey(clusn,newlast,newclus.clusn); // Set newlast in parent
  399.   rv=parent->add(last,clusn,i,0);                   // Add record before new one
  400.  }
  401.  else    // We have split the top block, make a new one
  402.  {
  403.   indclus *newparent=new indclus(-1,0,oi);        // New top block
  404.   newparent->clustyp=1;                    // Pointer block
  405.   newparent->add(last,clusn,-1,NOKEYHIGHER);        // add this block &
  406.   newparent->add(newlast,newclus.clusn,0,NOKEYHIGHER);  // add the new block
  407.   newparent->nclusrec=2;
  408.   *(long *)(newparent->clusdat)=1;        // update no. of records
  409.   oi->tblk=newparent->clusn;
  410.   oi->chng=1;
  411.  
  412.   // Now link in the new top block, we know that this record is the
  413.   // old top block, and newparent is the new one
  414.  
  415.   if (newparent->next) newparent->next->prev=newparent->prev;
  416.   if (newparent->prev) newparent->prev->next=newparent->next;
  417.  
  418.   oi->topind=newparent;
  419.   newparent->prev=0;
  420.   newparent->next=this;
  421.   prev=newparent;
  422.   parent=newparent;
  423.   newclus.parent=newparent;
  424.  }
  425.  
  426.  // Finally insert the new record
  427.  
  428.  if (irn>=nclusrec)    // Insert key in new cluster ?
  429.  {
  430.   if (irn==nclusrec) newclus.add(newkey,rn,0,0);
  431.   else
  432.   {
  433.    irn-=nclusrec;            // New position to insert key
  434.    newclus.add(newkey,rn,irn,rsk);    // Insert in new cluster
  435.   }
  436.  }
  437.  else    // Insert key in this cluster
  438.  {
  439.   if (irn==nclusrec) add(newkey,rn,irn-1,NOKEYHIGHER);
  440.   else add(newkey,rn,irn,0);
  441.  }
  442.  return newclus.clusn;
  443. }
  444.  
  445. // Change key value of pointer record in cluster to the supplied
  446. // new key for the supplied cluster no. also change cluster no if different
  447. // Return number of altered record
  448.  
  449. int indclus::newkey(long kclus,char *newkey,long newclus)
  450. {
  451.  char *cp=clusdat+4;
  452.  int i=0;
  453.  
  454.  while(*(long *)cp!=kclus) {cp+=reclen; i++;}
  455.  
  456.  *(long *)cp=newclus;
  457.  memmove(cp+8,newkey,explen);
  458.  change=1;
  459.  
  460.  // Now we check parent to see if we need to change the last record
  461.  // key as a result of this change
  462.  
  463.  if (i==nclusrec-1 && parent) parent->newkey(clusn,newkey,clusn);
  464.  return i;
  465. }
  466.